/**第一种用到了额外空间
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *temp = head;
        unordered_set<ListNode*> set;
        while (temp)
        {
            if (set.find(temp) != set.end())
                return temp;
            set.insert(temp);
            temp = temp -> next;
        }
        return NULL;
    }
};

/**龟兔赛跑法，无额外空间使用
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *tortoise = head, *hare = head;
        do
        {
            if (!hare || ! hare -> next)
                return NULL;
            tortoise = tortoise -> next;
            hare = hare -> next ->next;
        } while(tortoise != hare);
        tortoise = head;
        while(tortoise != hare)
        {
            tortoise = tortoise -> next;
            hare = hare -> next;
        }
        return hare;
    }
};
